package leetcode.code0873;

import java.util.HashMap;
import java.util.Map;

public class Solution extends Solution873 {

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

	@Override
	public int lenLongestFibSubseq(int[] arr) {
		int n = arr.length;
		Map<Integer, Integer> hash = new HashMap<>();
		for (int i = 0; i < n; i++) {
			hash.put(arr[i], i);
		}
		int ans = 0;
		Integer[][] dp = new Integer[n][n];
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				int num = arr[i] + arr[j];
				int k = hash.getOrDefault(num, -1);
				if (k != -1 && dp[j][k] == null) {
					if (dp[i][j] == null)
						dp[i][j] = 2;
					dp[j][k] = dp[i][j] + 1;
					ans = Math.max(ans, dp[j][k]);
				}
			}
		}
		return ans;
	}



}
